package kodkod.analysis;

import java.math.BigInteger;

public class PermutationGenerator {
	
	private int maxDigits;
	private BigInteger[] binSizes;
	
	public PermutationGenerator(int maxDigits) {
		this.maxDigits = maxDigits;
		this.binSizes = new BigInteger[maxDigits+1];
		// calculate binSizes
		BigInteger binSize = BigInteger.ONE;
		for (int i = 1; i <= maxDigits; i++) {
			binSize = binSize.multiply(new BigInteger(i+""));
			binSizes[maxDigits - i] = binSize;
		}
		binSizes[maxDigits] = BigInteger.ONE;
	}
	
	public int[] getPermutation(BigInteger permId) {
		int[] perm = new int[maxDigits];
		int[] iota = getIota(permId);
		
		for (int pos = maxDigits-1; pos >= 0; pos--) {
			int x = iota[pos];
			for (int pos2 = pos-1; pos2 >= 0; pos2--) {
				if (iota[pos2] <= x) x++;
			}
			perm[pos] = x+1;
		}
		
		return perm;
	}
	
	public BigInteger getMaxPermutation() {
		return binSizes[0];
	}
	
	public int[] getIota(BigInteger permId) {
		int[] iota = new int[maxDigits];
		
		for (int i = 0; i < maxDigits; i++) {
			iota[i] = permId.divide(binSizes[i+1]).mod(new BigInteger((maxDigits-i) + "")).intValue(); 
			//iota[i] = (int) ((permId / binSizes[i+1]) % (long)(maxDigits - i));
		}
		
		return iota;
	}
	
//	public int[] getIota(int permId) {
//		int[] iota = new int[maxDigits];
//		
//		int index = permId;
//		for (int i = 0; i < maxDigits; i++) {
//			index = index % binSizes[i];
//			iota[i] = index / binSizes[i+1];
//		}
//		
//		return iota;
//	}
}
